package com.xjh.basestudy.algorithmandexercise.sort;
/**
 应用场景:
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这
个时候就要用到一种新的排序方法——插入排序法.
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算
法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
 算法流程:
 插入算法把要排序的数组分成两部分：
 第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
 而第二部分就只包含这一个元素（即待插入元素）。
 在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：
 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。属于
稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。
一般来说，插入排序都采用in-place在数组上实现。
 具体算法描述如下：
 ⒈ 从第一个元素开始，该元素可以认为已经被排序
 ⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
 ⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
 ⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 ⒌ 将新元素插入到下一位置中
 ⒍重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的
一个变种，称为二分查找排序。
* */
public class InsertSort {
    private int[] sort(int[] arr) {
//如果传入的数组为空或者只有一个值,就直接返回

        if (arr == null || arr.length < 2) {
            return arr;
        }
//不为空则进循环判断
//外层循环控制总数量
        for (int i = 1; i < arr.length; i++) {//因为两个数比较一趟所以都是比较n-1趟
//内层循环依次减少并提出结果
            //内层循环两两比较,从后比到前,
            // 比如当j=3,j-1=2,此时先比较第四个和第三个元素,如果后一个<前一个,就把前一个换到前面来
            for (int j = i; j > 0; j--) {
//如果当前数字小于前一个,则交换,否则不变
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
        int[] array = {2, 5, 1, 6, 4, 9, 8, 5, 3, 1, 2, 0};
        int[] sort = insertSort.sort(array);
        for (int num : sort) {
            System.out.print(num + "\t");

        }
    }
}
